#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

class Solution {
public:
        ListNode* middleNode(ListNode* head) {
            ListNode* t = head;
            vector<ListNode*> list;
            while (t) {
                list.push_back(t);
                t = t->next;
            }
            int mid = ceil(list.size() / 2);
            return list[mid];
        }

    ListNode* middleNodeByFastSlowPointer(ListNode* head) {
        ListNode* slow = head, * fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

int main() {
    ListNode t1(1), t2(2),t3(3),t4(4),t5(5),t6(6);
    t1.next = &t2;//, t2.next = &t3, t3.next = &t4, t4.next = &t5, t5.next = &t6;
    Solution s;
    ListNode *r=s.middleNode(&t1);
    return 0;
}